Prior to the invention of public key cryptography, two parties that wished to communicate securely over an unsecured network needed to first establish a mutual secret out of band. While this might be acceptable for small organizations, such solutions are clearly infeasible in today's Internet with billions of users.
The concept of public key cryptography radically changed secure communication. In public key cryptography, two parties can securely communicate with each other without having an a priori mutual secret. Knowing only a party's globally shared public key, a user can verify that a message was sent by the party (using digital signatures) and confidentially encrypt a message to the intended party (using public key encryption).
Public key cryptography opened a floodgate of applications and the use of public key cryptography has become ubiquitous. Almost all major software vendors can now distribute software updates and security patches over the Internet. For example, digital signatures are a critical tool for enforcing that an update is from the legitimate vendor and not malware. Web browsers use public key encryption (via SSL) to send confidential information (e.g., credit card numbers, passwords, etc.) over the web to online services and modern email readers can send and receive encrypted email.
In this model, encryption is traditionally viewed as a mechanism for a user, Alice, to confidentially encode data to a target recipient, Bob. Alice encrypts the data under the recipient's public key such that only Bob, with knowledge of his private key, can decrypt it.
However, in some applications, it is desirable to share data according to an encryption policy without prior knowledge of who will be receiving the data. Functional encryption enables this. Suppose an informant needs to encrypt a message for anyone in a police department's internal affairs office or anyone who is undercover and in the central office—even though the informant may not know which officers satisfy these conditions. The informant will want to encrypt the message according to some other parameters, rather than to a specific individual. Using functional encryption, instead of encrypting data to a particular user, an encryptor can encrypt data under the public parameters of a system. To accomplish this, users in the system can obtain a private secret key (issued from an authority) that is associated with a value k. What a user learns about the data depends on the system's functionality and their key value k.
An example functional encryption system is known as attribute-based encryption (ABE). Attribute-based encryption is a type of public key encryption that allows users to encrypt and decrypt messages based on user attributes. In a (Key-Policy) ABE system, a private secret key is associated with a boolean formula φ and a ciphertext is associated with a pair of a message m and variables {right arrow over (x)}. A user can decrypt and learn m if and only if {right arrow over (x)} satisfies the formula φ.
This functionality comes at a cost. In a typical implementation, the size of the ciphertext is proportional to the number of attributes associated with it and the decryption time is proportional to the number of attributes used during decryption. Specifically, many practical ABE implementations require one pairing operation per attribute used during decryption. Existing techniques for constant pairings in decryption for an expressive (Key-Policy) ABE system are inefficient or work only in restricted settings. For example, some of those techniques use an inner product instance as a base building block which fundamentally required a bound, n, on the maximum number of attributes that can appear in a ciphertext. This choice of n forced a tradeoff between flexibility and performance.
Some existing systems require setting n high to cover the worst case scenarios. In those systems, the private secret key size blows up by a factor of n, the maximum number of attributes possible. Additionally, those systems have an added cost of |S| exponentiations during decryption for a ciphertext that encrypts with |S| attributes, which could be very costly in some situations. (As used herein, the notation |X| refers to the number of elements in set X.) For example, if Alice has the key policy (A1 AND A2) and receives a ciphertext with many attributes (A1, A2, . . . , A1000), Alice must do 1000 exponentiations which is computationally expensive. Existing systems also typically require that the number of multiplications is roughly |I|·|S|, the number of rows used in decryption times the number of attributes in a ciphertext.